Основы оптимизации
Безусловная оптимизация
Задачи безусловной оптимизации состоят в поиске максимума или минимума заданной функции при отсутствии каких-либо ограничений.
В этом разделе мы рассмотрим логистическую задачу нелинейной безусловной оптимизации по поиску оптимальной локации складского помещения.
В целях сокращения логистических расходов складское помещение должно быть размещено на оптимальном удалении от четырех предприятий, поставки на которые осуществляются с этого склада.
1. Создание нелинейной оптимизационной задачи
Нелинейная оптимизационная задача подразумевает наличие нелинейной целевой функции или нелинейных условий, наложенных на поиск оптимального решения, или обоих факторов одновременно.
Создание нелинейной оптимизационной задачи отличается от создания линейной оптимизационной задачи применением нелинейного решателя.
Для решения данной задачи мы используем оптимизационную библиотеку JuMP и нелинейный решатель Ipopt. Для их использования необходимо выполнить команду ниже:
using JuMP, Ipopt;
Ipopt (Interior Point OPTimizer) – библиотека для нелинейной оптимизации задач большой размерности. Подробную документацию по этой библиотеке можно найти на сайте.
С помощью библиотеки Ipopt оптимизационные задачи решаются методом внутренней точки (interior-point method), который позволяет решать выпуклые задачи оптимизации с условиями, заданными в виде неравенств. В этом методе исходную для поиска точку можно выбирать только внутри допустимой области.
✏️Задание 1
Создайте оптимизационную задачу, применив к ней нелинейный решатель Ipopt, и сохраните ее в переменной NL_prob.
Решение
NL_prob = Model(Ipopt.Optimizer)
✏️Задание 2
Создайте переменные x и y, определяющие позицию склада в двумерном пространстве, и присвойте их вашей оптимизационной задаче. Для текущей задачи через запятую необходимо указать, что значение переменных не может быть меньше нуля.
Решение
@variable(NL_prob, x >= 0);
@variable(NL_prob, y >= 0);
2. Ввод координат предприятий
Склад обслуживает 4 предприятия, имеющие разные координаты. Координаты можно ввести в виде соответствующих четырехэлементных векторов X и Y. Координаты следует перевести в тип float для осуществления последующих расчетов. Это можно сделать, добавив . после каждого значения.
Выполните команду ниже для ввода координат предприятий:
X = [23., 34., 45., 72.];
Y = [11., 61., 19., 38.];
3. Ввод начальных координат склада
В некоторых случаях для решения оптимизационных задач оптимизируемым переменным необходимо задать начальные значения. В данном случае вы можете присвоить переменным x и y произвольные значения. Начальные значения не повлияют на конечный результат.
Выполните команду ниже для ввода начальных координат оптимизируемых переменных x и y:
set_start_value(x, 1)
set_start_value(y, 1)
4. Создание нелинейной целевой функции
Для создания нелинейной целевой функции необходимо использовать команду @NLobjective(). В скобках через запятую указывается имя оптимизационной задачи, которой присваивается целевая функция, Min или Max для нахождения минимального или максимального значения и математическое выражение целевой функции.
Расчет расстояния между складом и отдельно взятым предприятием осуществляется с помощью теоремы Пифагора по разнице координат точек:
Для расчета расстояния между складом и всеми предприятиями необходимо повторить операцию с координатами всех предприятий и суммировать результат:
Целевым значением нашей задачи являются двумерные координаты оптимальной локации склада, при которых сумма расстояний от склада до всех предприятий () принимает минимальное значение.
✏️Задание 3
С помощью команды @NLobjective() создайте целевую функцию, содержащую описанное выше выражение для расчета суммы расстояний от склада до всех предприятий . Присвойте функцию оптимизационной задаче NL_prob.
Подсказка
Для суммирования расстояний между складом и всеми четырьмя предприятиями необходимо повторить операцию 4 раза. Этого можно достичь, задав цикл for i = 1:4 внутри скобок команды sum().
Решение
@NLobjective(NL_prob, Min, sum(sqrt((x - X[i])^2 + (y - Y[i])^2) for i = 1:4))
5. Решение нелинейной оптимизационной задачи
✏️Задание 4
Используйте команды optimize!(), print() и objective_value() для решения, вывода результата и целевого значения оптимизационной задачи NL_prob.
Решение
optimize!(NL_prob)
print(NL_prob)
objective_value(NL_prob)
✏️Задание 5
Используйте команду value() с аргументами x и y для получения координат оптимального расположения склада. Сохраните новые значения в переменных x_opt и y_opt.
Решение
x_opt = value(x)
y_opt = value(y)
6. Визуализация результатов
Для визуализации результатов на графике мы используем библиотеку Plots. Для ее использования необходимо выполнить команду ниже:
using Plots;
Задайте параметры графиков, запустив команду ниже:
gr(size=(1700, 700), legend=false, grid=true, widen=1.5, ticks = 20)
Отобразите позиции предприятий на графике. Внутри команды plot вы можете задать дополнительные параметры визуализации, такие как форма, цвет и размер маркера.
Plots.plot(X, Y, seriestype=:scatter,markershape=:hexagon, color = :orange, markersize = 5, markerstrokewidth=1, aspect_ratio = :equal)
Отобразите оптимальную позицию склада на том же графике. Для этого используйте ! после команды plot. Вы можете изменить параметры визуализации внутри команды plot для наглядности.
Обратите внимание, что получив координаты x_opt и y_opt с помощью команды value(), мы изменили тип переменной и нам нужно заключить их в [] для передачи в команду plot().
plot!([x_opt], [y_opt], seriestype=:scatter,markershape=:diamond, color = :green, markersize = 5, markerstrokewidth=1)
Вы также можете вывести дополнительные пояснения на график.
ptstr = string([x_opt y_opt])
xvalstr = string(" Оптимальная локация")
annotate!(([x_opt y_opt]...,text(xvalstr, 13, :left, :black)))